import collections
import itertools
import operator
import random
import sys
import compass

def create(*values):
    """Creates a new extension wrapping the given value."""
    def iterate(values):
        for item in values:
            yield item
    return IterableExtender(iterate(values))

def extend(iterable):
    """Wraps an iterable with the extension class."""
    return IterableExtender(iterable)

def forever(factory):
    """Gets the result of calling the factory every time an item is requested."""
    if not callable(factory): raise TypeError("A factory method is required.")
    def spool(factory):
        while True:
            yield factory()
    return IterableExtender(spool(factory))

class IterableExtender(collections.Iterable):
    """Wraps a collection, providing an assortment of algorithms."""
    
    __iteratorResult = collections.namedtuple("__iteratorResult", ['Value', 'HadMore'])
    
    @staticmethod
    def __next(iterator):
        try:
            item = next(iterator)
            return IterableExtender.__iteratorResult(Value = item, HadMore = True)
        except StopIteration:
            return IterableExtender.__iteratorResult(Value = None, HadMore = False)
    
    def __init__(self, iterable):
        """Initializes a new instance of an IterableExtender"""
        if not isinstance(iterable, collections.Iterable): raise TypeError("A iterable collection is required.")
        self.__iterable = iterable
        
    def __iter__(self):
        return iter(self.__iterable)
        
    @property
    def iterable(self):
        """Gets the underlying iterable."""
        return self.__iterable
    
    def aggregate(self, aggregator, seed):
        """
        Aggregates the items in the iterable.
        agruments:
            aggregator - Combines the next item in the iterable with the running aggregate (default = +).
            seed - The starting value for the aggregate (default = 0).
        returns:
            The aggregate and the number of items iterated.
        """
        if aggregator is None: raise ValueError("The aggregator must not be None.")
        return IterableExtender.__aggregate(self.__iterable, aggregator, seed)
    
    @staticmethod
    def __aggregate(iterable, aggregator, seed):
        count = 0
        result = seed
        for item in iterable:
            count += 1
            result = aggregator(result, item)
        return (result, count)
    
    def all(self, predicate = bool):
        """Determines whether all of the items in the iterable satisfy the predicate."""
        if predicate is None: raise ValueError("The predicate must not be None.")
        if not callable(predicate): raise TypeError("A callable predicate is required.")
        return IterableExtender.__all(self.__iterable, predicate)
    
    @staticmethod
    def __all(iterable, predicate):
        for item in iterable:
            if not predicate(item):
                return False
        return True
    
    def any(self):
        """Determines whether there are any items."""
        return IterableExtender.__any(self.__iterable)
    
    @staticmethod
    def __any(iterable):
        iterator = iter(iterable)
        result = IterableExtender.__next(iterator)
        return result.HadMore
        
    def compare(self, other, comparison=compass.cmp):
        if other is None: raise ValueError("The other iterable must not be None.")
        if not isinstance(other, collections.Iterable): raise TypeError("Other must be an Iterable.")
        if comparison is None: raise ValueError("The comparison must not be None.")
        if not callable(comparison): raise TypeError("The comparison must be callable.")
        return IterableExtender.__compare(self.__iterable, other, comparison)
    
    @staticmethod
    def __compare(first, second, comparison):
        firstIterator = iter(first)
        secondIterator = iter(second)
        firstResult = IterableExtender.__next(firstIterator)
        secondResult = IterableExtender.__next(secondIterator)
        # by the time we leave this loop, we know all iterated items matched
        while firstResult.HadMore and secondResult.HadMore:
            result = comparison(firstResult.Value, secondResult.Value)
            if result != 0: return result
            firstResult = IterableExtender.__next(firstIterator)
            secondResult = IterableExtender.__next(secondIterator)
        if firstResult.HadMore: return 1 # the first iterable was longer
        elif secondResult.HadMore: return -1 # the second iterable was longer
        else: return 0 # the iterables were the same length and all items matched
    
    def concatenate(self, other):
        """Concatenates the items from the other iterable onto the iterable."""
        if other is None: raise ValueError("The other iterable must not be None.")
        if not isinstance(other, collections.Iterable): raise TypeError("Other must be an Iterable.")
        return extend(itertools.chain(self.__iterable, other))
    
    def contains(self, item, comparison = operator.eq):
        """Determines whether the given item is in the iterable."""
        if comparison is None: raise ValueError("The comparison must not be None.")
        return IterableExtender.__contains(self.__iterable, item, comparison)
    
    @staticmethod
    def __contains(iterable, value, comparison):
        for item in iterable:
            if comparison(item, value):
                return True
        return False
    
    def count(self):
        """Gets the number of items in the iterable."""
        return IterableExtender.__count(self.__iterable)
    
    @staticmethod
    def __count(iterable):
        soFar = 0
        for _ in iterable:
            soFar += 1
        return soFar
    
    def distinct(self, keySelector=(lambda x: x)):
        """Gets all of the items in the iterable with unique keys."""
        if keySelector is None: raise ValueError("The key selector must not be None.")
        if not callable(keySelector): raise TypeError("A callable key selector is required.")
        return extend(IterableExtender.__distinct(self.__iterable, keySelector))
    
    @staticmethod
    def __distinct(iterable, keySelector):
        lookup = set()
        for item in iterable:
            key = keySelector(item)
            if key not in lookup:
                yield item
                lookup.add(key)
    
    def equals(self, other, comparison=operator.eq):
        """Determines whether two iterables contain the same items."""
        if other is None: raise ValueError("Other must not be None.")
        if not isinstance(other, collections.Iterable): raise TypeError("Other must be iterable.")
        if comparison is None: raise ValueError("The comparison must not be None.")
        if not callable(comparison): raise TypeError("A callable comparison must be provided.")
        return IterableExtender.__equals(self.__iterable, other, comparison)
    
    @staticmethod
    def __equals(first, second, comparison):
        firstIterator = iter(first)
        secondIterator = iter(second)
        firstResult = IterableExtender.__next(firstIterator)
        secondResult = IterableExtender.__next(secondIterator)
        while firstResult.HadMore and secondResult.HadMore:
            result = comparison(firstResult.Value, secondResult.Value)
            if not result: return False
            firstResult = IterableExtender.__next(firstIterator)
            secondResult = IterableExtender.__next(secondIterator)
        return (not firstResult.HadMore) and (not secondResult.HadMore)
    
    def first(self):
        """Gets the first item in the iterable."""
        return IterableExtender.__first(self.__iterable)
    
    @staticmethod
    def __first(iterable):
        iterator = iter(iterable)
        result = IterableExtender.__next(iterator)
        if not result.HadMore:
            raise ValueError("The iterable was empty.")
        return result.Value
    
    def firstOrDefault(self, default=None):
        """Gets the first item in the iterable, or the default value if the iterable is empty."""
        return IterableExtender.__firstOrDefault(self.__iterable, default)
    
    @staticmethod
    def __firstOrDefault(iterable, default):
        iterator = iter(iterable)
        result = IterableExtender.__next(iterator)
        if result.HadMore:
            return result.Value
        else:
            return default
    
    def flatten(self):
        """Flattens an iterable of iterables into a single iterable."""
        return extend(IterableExtender.__flatten(self.__iterable))
    
    @staticmethod
    def __flatten(iterable):
        for item in iterable:
            for subItem in item:
                yield subItem
                
    def forEach(self, action):
        """Performs an action on each item in the iterable."""
        if action is None: raise ValueError("The action must not be None.")
        if not callable(action): raise TypeError("A callable action is required.")
        IterableExtender.__forEach(self.__iterable, action)
        
    @staticmethod
    def __forEach(iterable, action):
        for item in iterable:
            action(item)
    
    def groupBy(self, keySelector):
        """Groups the items by the key returned by the key selector."""
        if keySelector is None: raise ValueError("The key selector must not be None.")
        if not callable(keySelector): raise TypeError("A callable key selector is required.")
        return extend(IterableExtender.__groupBy(self.__iterable, keySelector, lambda x: x))
    
    @staticmethod
    def __groupBy(iterable, keySelector, valueSelector):
        lookup = {}
        for item in iterable:
            key = keySelector(item)
            value = valueSelector(item)
            values = lookup.setdefault(key, [])
            values.append(value)
        for key, values in lookup.items():
            yield Grouping(key, values)
    
    def last(self):
        """Gets the last item in the iterable."""
        return IterableExtender.__lastOptimized(self.__iterable)
    
    @staticmethod
    def __lastOptimized(iterable):
        if isinstance(iterable, collections.Sequence): 
            if len(iterable) == 0:
                raise ValueError("The iterable was empty.")
            else:
                return iterable[-1]
        else: 
            return IterableExtender.__last(iterable)
    
    @staticmethod
    def __last(iterable):
        # make sure the iterable has at least one item
        iterator = iter(iterable)
        result = IterableExtender.__next(iterator)
        if not result.HadMore:
            raise ValueError("The iterable was empty.")
        
        # assume we're looking at the last item and try moving to the next
        item = result.Value
        for item in iterator: 
            pass
        return item
    
    def lastOrDefault(self, default=None):
        """Gets the last item in the iterable, or the default if the iterable is empty."""
        return IterableExtender.__lastOrDefaultOptimized(self.__iterable, default)
    
    @staticmethod
    def __lastOrDefaultOptimized(iterable, default):
        if isinstance(iterable, collections.Sequence):
            return default if len(iterable) == 0 else iterable[-1]
        else:
            return IterableExtender.__lastOrDefault(iterable, default)
        
    @staticmethod
    def __lastOrDefault(iterable, default):
        iterator = iter(iterable)
        result = IterableExtender.__next(iterator)
        if not result.HadMore: 
            return default
        
        # assume we're looking at the last item and try moving to the next
        item = result.Value
        result = IterableExtender.__next(iterator)
        while result.HadMore:
            item = result.Value
            result = IterableExtender.__next(iterator)
        return item
    
    def map(self, mapper):
        """Maps the values in the iterable to values in a new iterable."""
        if mapper is None: raise ValueError("The mapper must not be None.")
        if not callable(mapper): raise TypeError("A callable mapper is required.")
        # once we're to Python 3, we need to replace this with 'map'
        return extend(IterableExtender.__map(self.__iterable, mapper))
    
    @staticmethod
    def __map(iterable, mapper):
        for item in iterable:
            yield mapper(item)
    
    def max(self, comparison=compass.cmp):
        """Gets the largest item in the iterable."""
        if comparison is None: raise ValueError("The comparison must not be None.")
        if not callable(comparison): raise TypeError("A callable comparison is required.")
        return IterableExtender.__max(self.__iterable, comparison)
    
    @staticmethod
    def __max(iterable, comparison):
        iterator = iter(iterable)
        result = IterableExtender.__next(iterator)
        if not result.HadMore:
            raise ValueError("The iterable was empty.")
        max = result.Value
        result = IterableExtender.__next(iterator)
        while result.HadMore:
            value = result.Value
            if comparison(max, value) < 0:
                max = value
            result = IterableExtender.__next(iterator)
        return max
    
    def min(self, comparison=compass.cmp):
        """Gets the smallest item in the iterable."""
        if comparison is None: raise ValueError("The comparison must not be None.")
        if not callable(comparison): raise TypeError("A callable comparison is required.")
        return IterableExtender.__min(self.__iterable, comparison)
    
    @staticmethod
    def __min(iterable, comparison):
        iterator = iter(iterable)
        result = IterableExtender.__next(iterator)
        if not result.HadMore:
            raise ValueError("The iterable was empty.")
        min = result.Value
        result = IterableExtender.__next(iterator)
        while result.HadMore:
            value = result.Value
            if comparison(min, value) > 0:
                min = value
            result = IterableExtender.__next(iterator)
        return min
        
    def order(self, keySelector=(lambda x: x), reverse=False):
        """Orders the items in the iterable by comparing the keys."""
        if keySelector is None: raise ValueError("The key selector must not be None.")
        if not callable(keySelector): raise TypeError("A callable key selector is required.")
        if not isinstance(reverse, bool): raise TypeError("reverse must be a bool.")
        asList = IterableExtender.__toListOptimized(self.iterable)
        asList.sort(key=keySelector, reverse=reverse)
        return extend(asList)
    
    def partition(self, predicate=bool):
        """Divides the iterable into two iterables, the first containing the items that satisfied the predicate."""
        if predicate is None: raise ValueError("The predicate must not be None.")
        if not callable(predicate): raise TypeError("A callable predicate is required.")
        matches, unmatches = IterableExtender.__partition(self.__iterable, predicate)
        return extend(matches), extend(unmatches)
    
    @staticmethod
    def __partition(iterable, predicate):
        matches = []
        unmatches = []
        for item in iterable:
            if predicate(item):
                matches.append(item)
            else:
                unmatches.append(item)
        return matches, unmatches
    
    def randomSamples(self, sampleCount=1, generator=(lambda x: int(random.random() * x))):
        """Retrieves the requested number of samples from the iterable at random."""
        if not isinstance(sampleCount, int): raise TypeError("The sample count must be an integer.")
        if sampleCount < 0: raise ValueError("The sample count must not be negative.")
        if generator is None: raise ValueError("The generate must not be None.")
        if not callable(generator): raise TypeError("A callable generator is required.")
        return extend(IterableExtender.__randomSamples(self.__iterable, sampleCount, generator))
    
    @staticmethod
    def __randomSamples(iterable, sampleCount, generator):
        samples = []
        iterator = iter(iterable)
        # fill up the samples with the items from the beginning of the iterable
        result = IterableExtender.__next(iterator)
        while len(samples) != sampleCount and result.HadMore:
            samples.append(result.Value)
            result = IterableExtender.__next(iterator)
        # replace items if the generated number is less than the total
        total = len(samples)
        while result.HadMore:
            total += 1
            likelihood = generator(total)
            if likelihood < sampleCount:
                samples[likelihood] = result.Value
            result = IterableExtender.__next(iterator)
        return samples
    
    def reverse(self):
        """Reverses the iterable."""
        return extend(IterableExtender.__reverseOptimized(self.__iterable))
    
    @staticmethod
    def __reverseOptimized(iterable):
        if isinstance(iterable, collections.Sequence):
            return reversed(iterable)
        else:
            return IterableExtender.__reverse(iterable)
        
    @staticmethod
    def __reverse(iterable):
        stack = []
        for item in iterable:
            stack.append(item)
        while len(stack) != 0:
            yield stack.pop()
    
    def rotateLeft(self, shift=1):
        """Rotates the items in the iterable to the left."""
        if not isinstance(shift, int): raise TypeError("The shift amount must be an integer.")
        if shift == 0: return self
        return extend(IterableExtender.__rotateLeft(self.__iterable, shift))
    
    @staticmethod
    def __rotateLeft(iterable, shift):
        iterable = IterableExtender.__toListOptimized(iterable)
        length = len(iterable)
        shift %= length
        if shift < 0: shift += length
        front = shift
        while front != length:
            yield iterable[front]
            front += 1
        front = 0
        while front != shift:
            yield iterable[front]
            front += 1
    
    def single(self):
        """Gets the first item in the iterable, raising an exception if there is more than one item."""
        return IterableExtender.__single(self.__iterable)
    
    @staticmethod
    def __single(iterable):
        # try moving to the first item
        iterator = iter(iterable)
        result = IterableExtender.__next(iterator)
        if not result.HadMore:
            raise ValueError("The iterable was empty.")
        item = result.Value
        # see if there is more than one item
        result = IterableExtender.__next(iterator)
        if result.HadMore:
            raise ValueError("The iterable had more than one item.")
        return item
    
    def singleOrDefault(self, default):
        """
        Gets the first item in the iterable, 
        returning the default if the iterable is empty 
        and raising an exception if there is is more than one item.
        """
        return IterableExtender.__singleOrDefault(self.__iterable, default)
    
    @staticmethod
    def __singleOrDefault(iterable, default):
        # try moving to the first item
        iterator = iter(iterable)
        result = IterableExtender.__next(iterator)
        if not result.HadMore:
            return default
        item = result.Value
        # see if there is more than one item
        result = IterableExtender.__next(iterator)
        if result.HadMore:
            raise ValueError("The iterable had more than one item.")
        return item
    
    def skip(self, count=1):
        """Skips the given number of items and returns the remaining."""
        if not isinstance(count, int): raise TypeError("The count must be an integer.")
        if count < 0: count = 0
        return extend(itertools.islice(self.__iterable, count, sys.maxsize))
    
    def skipWhile(self, predicate=bool):
        """Skips the items in the iterable until an item satisfying the predicate is found."""
        if predicate is None: raise ValueError("The predicate must not be None.")
        if not callable(predicate): raise TypeError("A callable predicate is required.")
        return extend(itertools.dropwhile(predicate, self.__iterable))
    
    def take(self, count=1):
        """Takes the given number of items from the iterable."""
        if not isinstance(count , int): raise TypeError("The count must be an integer.")
        if count < 0: count = 0
        return extend(itertools.islice(self.__iterable, count))
        
    def takeWhile(self, predicate=bool):
        """Takes the items from the iterable while the predicate holds."""
        if predicate is None: raise ValueError("The predicate must not be None.")
        if not callable(predicate): raise TypeError("A callable predicate is required.")
        return extend(itertools.takewhile(predicate, self.__iterable))
    
    def toDict(self, keySelector=(lambda x: x), valueSelector=(lambda x: x)):
        """Creates a dictionary from the iterable, using the key and value selectors."""
        if keySelector is None: raise ValueError("The key selector must not be None.")
        if not callable(keySelector): raise TypeError("A callable key selector is required.")
        if valueSelector is None: raise ValueError("The value selector must not be None.")
        if not callable(valueSelector): raise TypeError("A callable value selector is required.")
        return IterableExtender.__toDict(self.__iterable, keySelector, valueSelector)
    
    @staticmethod
    def __toDict(iterable, keySelector, valueSelector):
        return {keySelector(x): valueSelector(x) for x in iterable}
    
    def toFrozenSet(self):
        """Creates a frozen set from the iterable."""
        return IterableExtender.__toFrozenSetOptimized(self.__iterable)
    
    @staticmethod
    def __toFrozenSetOptimized(iterable):
        if isinstance(iterable, set): return iterable
        else: return IterableExtender.__toFrozenSet(iterable)
        
    @staticmethod
    def __toFrozenSet(iterable):
        return frozenset(iterable)
    
    def toList(self):
        """Creates a list from the iterable."""
        return IterableExtender.__toListOptimized(self.__iterable)
    
    @staticmethod
    def __toListOptimized(iterable):
        if isinstance(iterable, list): return iterable
        else: return IterableExtender.__toList(iterable)
    
    @staticmethod
    def __toList(iterable):
        return list(iterable)
    
    def toLookup(self, keySelector=(lambda x: x), valueSelector=(lambda x: x)):
        """Creates a lookup from the iterable, using the key and value selectors."""
        if keySelector is None: raise ValueError("The key selector must not be None.")
        if not callable(keySelector): raise TypeError("A callable key selector is required.")
        if valueSelector is None: raise ValueError("The value selector must not be None.")
        if not callable(valueSelector): raise TypeError("A callable value selector is required.")
        groups = IterableExtender.__groupBy(self.__iterable, keySelector, valueSelector)
        return Lookup(groups)
    
    def toSet(self):
        """Creates a set from the iterable."""
        return IterableExtender.__toSetOptimized(self.__iterable)
    
    @staticmethod
    def __toSetOptimized(iterable):
        if isinstance(iterable, set): return iterable
        else: return IterableExtender.__toSet(iterable)
        
    @staticmethod
    def __toSet(iterable):
        return set(iterable)
    
    def toTuple(self):
        """Creates a tuple from the iterable."""
        return IterableExtender.__toTupleOptimized(self.__iterable)
    
    @staticmethod
    def __toTupleOptimized(iterable):
        if isinstance(iterable, tuple): return iterable
        else: return IterableExtender.__toTuple(iterable)
        
    @staticmethod
    def __toTuple(iterable):
        return tuple(iterable)
    
    def where(self, predicate = bool):
        """Gets the items in the iterable satisfying the given predicate, wrapped."""
        if predicate is None: raise ValueError("The predicate must not be null.")
        if not callable(predicate): raise TypeError("A callable predicate is required.")
        # replace this with filter when to Python 3
        return extend(IterableExtender.__where(self.__iterable, predicate))
    
    @staticmethod
    def __where(iterable, predicate):
        for item in iterable:
            if predicate(item):
                yield item
                
    def zip(self, other, zipper):
        """Combines the iterable with the other iterable by applying the zipper to the items from both iterables."""
        if other is None: raise ValueError("The other iterable must not be None.")
        if not isinstance(other, collections.Iterable): raise TypeError("Other must be an iterable.")
        if zipper is None: raise ValueError("The zipper must not be None.")
        if not callable(zipper): raise TypeError("A callable zipper is required.")
        # replace with zip when to Python 3
        return extend(IterableExtender.__zip(self.__iterable, other, zipper))
    
    @staticmethod
    def __zip(first, second, zipper):
        firstIterator = iter(first)
        secondIterator = iter(second)
        firstResult = IterableExtender.__next(firstIterator)
        secondResult = IterableExtender.__next(secondIterator)
        while firstResult.HadMore and secondResult.HadMore:
            yield zipper(firstResult.Value, secondResult.Value)
            firstResult = IterableExtender.__next(firstIterator)
            secondResult = IterableExtender.__next(secondIterator)
    
class Grouping(IterableExtender):
    """Represents a group of values, associated with a key."""
    
    def __init__(self, key, values):
        """Initializes a new instance of a Grouping."""
        IterableExtender.__init__(self, values)
        self.__key = key
        
    @property
    def key(self):
        """Gets the key associated with the group."""
        return self.__key
    
class Lookup(IterableExtender):
    """Represents a grouping of values that can be looked up by key."""
    
    def __init__(self, groupings):
        """Initializes a new instance of a Lookup."""
        IterableExtender.__init__(self, groupings)
        groups = { grouping.key: grouping for grouping in groupings }
        self.__groups = groups
        
    def __getitem__(self, key):
        """Gets the values associated to the given key."""
        if key in self.__groups: 
            group = self.__groups[key]
            return extend(group.iterable)
        else:
            return create()